/**
 * 第 N 个神奇数字
 * <pre>
 * 一个正整数如果能被 a 或 b 整除，那么它是神奇的。
 * 给定三个整数 n ,a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案对109+ 7 取模后的值。
 * 示例 1：
 * 输入：n = 1, a = 2, b = 3
 * 输出：2
 * 示例2：
 * 输入：n = 4, a = 2, b = 3
 * 输出：6
 * 提示：
 * 1 <= n <= 10<sup>9</sup>
 * 2 <= a, b <= 4 * 10<sup>4</sup>
 * </pre>
 */
public class NthMagicalNumber_878 extends AbsSolution
{
    // TODO 二分查找补课后再来研究

    /*
    2: 2 | 4 6
    3:   3

    2: 2 4 6 8
    4:

    4: 4 | 8 |12
    6:   6    12

    4: 4, 5, 8, 10, 12, 15, 16, 20
    5:

5,8: 5, 8, 10, 15, 16, 20, 24, 25, 30, 32, 35, 40
     0  1  2   3   4   5   6   7   8   9   10  11
     0     1   2       3       4   5       6   7
        0          1       2           3

    3: 3 6 | 9 12 15| 18 21 |24| 27 30 | 33 36 39 | 42 45 |48| 51 54
    8:     8       16        24       32         40        48
     */

    public static NthMagicalNumber_878 getInstance()
    {
        return new NthMagicalNumber_878();
    }

    public int nthMagicalNumber2(int n, int a, int b)
    {
        // TODO 二分查找
        long lcm = (long) a * b / gcd(a, b);
        long left = 0, right = (long) Math.max(a, b) * n; // 开区间 (left, right)
        while (left + 1 < right) { // 开区间不为空
            long mid = (left + right) / 2;
            if (mid / a + mid / b - mid / lcm >= n) {
                right = mid; // 范围缩小到 (left, mid)
            }
            else {
                left = mid; // 范围缩小到 (mid, right)
            }
        }
        return (int) (right % MOD);
    }

    public int nthMagicalNumber(int n, int a, int b)
    {
        int lcm = a / gcd(a, b) * b;
        // 一轮长度
        int loopLen = lcm / a + lcm / b - 1;
        // 完整轮数
        int loops = n / loopLen;
        int left = n % loopLen;

        int leftValue = 0; // 循环中的哪个值

        // 交替步长
        if (left == 0) {
            leftValue = 0;
        }
        else {
            int min = Math.min(a, b);
            int max = Math.max(a, b);
            if (max % min == 0) {
                leftValue = left * min;
            }
            else {
                int l = min, r = min * left;
                while (l <= r) {
                    int mid = (l + r) / 2;
                }
            }
        }

        return mod((long) lcm * (n / loopLen) + leftValue);
    }

}
